Neural networks are nowadays highly successful despite strong hardness results. The existing hardness results focus on the network architecture, and assume that the network's weights are arbitrary. A natural approach to settle the discrepancy is to assume that the network's weights are ``well-behaved and posses some generic properties that may allow efficient learning. This approach is supported by the intuition that the weights in real-world networks are not arbitrary, but exhibit some ''random-like properties with respect to some ''natural distributions. We prove negative results in this regard, and show that for depth-$2$ networks, and many ``natural weights distributions such as the normal and the uniform distribution, most networks are hard to learn. Namely, there is no efficient learning algorithm that is provably successful for most weights, and every input distribution. It implies that there is no generic property that holds with high probability in such random networks and allows efficient learning.

Additional Feedback: In this paper the authors consider the following question: what is an important aspect of a neural network that makes it work well in practice when it's known to be theoretically hard to learn neural networks. There have been many prior works in this direction but most works have proved hardness of learning neural networks under strange architectures or distributions. In this paper their main contribution is to look at "natural" distributions which include for example the uniform distribution and normal distribution and show hardness of learning neural networks even under such natural distributions. Given how important neural networks are in practice, understanding their theoretical underpinning is an important question in ML and this paper shows yet another direction in which it is hard to learn NNs. The main selling point is that prior works looked at arbitrary weights, solely with the purpose of proving lower bounds but in this paper the authors look at natural weights (under which one might have expected to prove positive results) and show that even in this setting, NNs are hard to learn.

The paper received four reviews. Initially, the scores were borderline but more on the side of accepting. The reviews point out that the paper provides a new style of results on a fundamentally important problem, with interesting techniques. However, one reviewer commented on the result itself being unsurprising; two reviewers were critical of the fact that the result depends on a worst-case input distribution; and some concern was expressed about relation to previous work. The reply from the authors was considered by the reviewers mainly satisfactory, but only partially so regarding the worst-case input distribution.

Neural networks are nowadays highly successful despite strong hardness results. The existing hardness results focus on the network architecture, and assume that the network's weights are arbitrary. A natural approach to settle the discrepancy is to assume that the network's weights are well-behaved" and posses some generic properties that may allow efficient learning. This approach is supported by the intuition that the weights in real-world networks are not arbitrary, but exhibit some ''random-like" properties with respect to some ''natural" distributions. We prove negative results in this regard, and show that for depth- 2 networks, and many natural" weights distributions such as the normal and the uniform distribution, most networks are hard to learn.